package sort_code;

import java.util.ArrayList;

//插入排序，先确定有序和无序，依次取无序中的数，然后从后往前对比插入有序中
public class Insert {
    public static void main(String[] args) {
        int[] arr = {4,7,1,2,9,3,10,5,8,6};

        int startIndex = -1;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] > arr[i+1]){
                startIndex = i + 1;
                break;
            }
        }
//         方法一
//        for (int i = startIndex; i < arr.length; i++) {
//            for (int j = i; j > 0; j--) {
//                if(arr[j-1] > arr[j]){
//                    int tmp = arr[j-1];
//                    arr[j-1] = arr[j];
//                    arr[j] = tmp;
//                }
//            }
//        }

        //方法二
        for (int i = startIndex; i < arr.length; i++) {
            int j = i;
            while(j > 0 && arr[j-1] > arr[j]){
                int tmp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = tmp;
                j--;
            }
        }


        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}
